package Leetcode.ArrayAndLinkedList.threeSum15;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 该题解法 双指针法
 * 先判断传入的nums是否有效 即不能为null 长度不能小于3
 * 先将该数组排序
 * 固定下标i得值 在i的右侧 head指向i+1 tail指向len-1
 * sum = nums[i] + nums[head] + nums[tail]
 * 如果sum<0 则小数太小 则head往右即大数方向移动
 * 如果sum》0 则大数太大  则tail往左即小数方向移动
 * 如果sum = 0 则将其放入到list中 并head++ tail-- 往中心汇合
 * 如果汇合途中head+1 或者tail-1 则重复 因为i是固定的 另外两个数如果有一个重复 那这两种组合必定重复
 * 需要跳过 再让head++ tail--直到head 和 tail 相遇 即需要head < tail
 * 这样一圈找完后 则该固定i下已经全部找完 则需改动i的值 则让i++ 如果i+1的值和i的值相同
 * 则重复 需要跳过  重复的原因在于 三个数 如果一个数相同那另外两个数的组合方式必定相同
 */

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        int len = nums.length;
        if (len < 3 || nums == null) {
            return list;
        }
        Arrays.sort(nums);
        for (int i = 0; i < len; i++) {
            if (nums[i] > 0) {
                break;
            }
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int head = i + 1;
            int tail = len - 1;
            while (head < tail) {
                int sum = nums[i] + nums[head] + nums[tail];
                if (sum == 0) {
                    list.add(Arrays.asList(nums[i], nums[head], nums[tail]));
                    //head < tail 此处作用既是head tail交汇 即重复 也是为了避免下标越界
                    while (head < tail && nums[head] == nums[head + 1]) {
                        head++;
                    }
                    while (head < tail && nums[tail] == nums[tail - 1]) {
                        tail--;
                    }
                    head++;
                    tail--;
                }
                if (sum < 0) {
                    head++;
                }
                if (sum > 0) {
                    tail--;
                }
            }
        }
        return list;
    }

    public static void main(String[] args) {
        int[] numList = {0, 0, 0};
        Solution solution = new Solution();
        System.out.println(solution.threeSum(numList));
    }
}

